#include "BinaryTree.h"
#include <queue>

BinaryTree::BinaryTree()
:root(nullptr)
{
    init();
}
BinaryTree::~BinaryTree() {
    deinit();
}

void BinaryTree::init(){
    root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);

    root->left->left = new Node(4);
    root->left->right = new Node(5);

    root->right->left = new Node(6);
    root->right->right = new Node(7);
}

void freePreorder(BinaryTree::Node * node){
    if(node != nullptr){
        freePreorder(node->left);
        freePreorder(node->right);
        delete node;
    }
}
void freeInorder(BinaryTree::Node * node){
    if(node != nullptr){
        freeInorder(node->left);
        auto * right = node->right;
        delete node;
        freeInorder(right);
    }
}
void freePostorder(BinaryTree::Node * node){
    if(node != nullptr){
        freePostorder(node->left);
        freePostorder(node->right);
        delete node;
    }
}

void BinaryTree::deinit(){
    freePreorder(root);
    //freeInorder(root);
    //freePostorder(root);
    root = nullptr;
}



void BinaryTree::levelTraversal(){
    std::cout << "BinaryTree::levelTraversal:" << std::endl;
    std::queue<Node*> levelQueue;

    if(root != nullptr){
        levelQueue.push(root);
        while(!levelQueue.empty()){
            auto * ptr = levelQueue.front();
            std::cout << ptr->value << ", ";
            levelQueue.pop();
            if(ptr->left != nullptr){
                levelQueue.push(ptr->left);
            }
            if(ptr->right != nullptr){
                levelQueue.push(ptr->right);
            }
        }
        std::cout << std::endl;
    }
}

static void preorder(BinaryTree::Node * node){
    if(node != nullptr){
        std::cout << node->value << ", ";
        preorder(node->left);
        preorder(node->right);
    }
}
void BinaryTree::preorderTraversal() {
    std::cout << "BinaryTree::preorderTraversal:" << std::endl;
    preorder(root);
    std::cout << std::endl;
}

static void inorder(BinaryTree::Node * node){
    if(node != nullptr){
        inorder(node->left);
        std::cout << node->value << ", ";
        inorder(node->right);
    }
}
void BinaryTree::inorderTraversal(){
    std::cout << "BinaryTree::inorderTraversal:" << std::endl;
    inorder(root);
    std::cout << std::endl;
}
static void postorder(BinaryTree::Node * node){
    if(node != nullptr){
        postorder(node->left);
        postorder(node->right);
        std::cout << node->value << ", ";
    }
}
void BinaryTree::postorderTraversal(){
    std::cout << "BinaryTree::postorderTraversal:" << std::endl;
    postorder(root);
    std::cout << std::endl;
}


static BinaryTree::Node * createTree(int * preFirst, int * preLast, int * inFirst, int * inLast){
    if(preLast < preFirst || inLast < inFirst){
        return nullptr;
    }

    BinaryTree::Node * node = new BinaryTree::Node(preFirst[0]);
    
    //2. find preFirst[0] in inOrder
    int * ptr = inFirst;
    while(ptr != inLast && preFirst[0] != *ptr){
        ++ptr;
    }
    
    int leftLength = ptr - inFirst;
    if(leftLength > 0){
        node->left = createTree(preFirst + 1, preFirst + leftLength, inFirst, inFirst + leftLength - 1);
    }
    int rightLength = inLast - ptr;
    if(rightLength> 0){
        node->right = createTree(preFirst + leftLength + 1, preLast, inFirst +leftLength+1, inLast);
    }
    return node; 
}

BinaryTree::Node * BinaryTree::construct(int * preStart, int preLength, int * inStart, int inLength) {
    assert(preLength == inLength);
    if(preLength > 0 && preStart != nullptr && inStart != nullptr){
        return createTree(preStart, preStart + preLength - 1, inStart, inStart + inLength - 1);
    }
    return nullptr;
}

void BinaryTree::run(){
    BinaryTree tree;
    tree.levelTraversal();
    tree.preorderTraversal();
    tree.inorderTraversal();
    tree.postorderTraversal();
    
    {
        int preOrder[] = {1, 2, 4, 5, 3, 6, 7,};
        int inOrder [] = {4, 2, 5, 1, 6, 3, 7,};
        Node * newRoot = tree.construct(preOrder, sizeof(preOrder)/sizeof(int), inOrder, sizeof(inOrder)/sizeof(int));
        assertTrue(newRoot != nullptr);
        std::cout << "This is newRoot of postorder traversal:" << std::endl;
        postorder(newRoot); std::cout << std::endl;
        std::cout << "equal to next postorder traversal:" << std::endl;
        tree.postorderTraversal();
        freeInorder(newRoot);
    }

    {
        int preOrder[] = {1, 2};
        int inOrder [] = {2, 1};
        Node * newRoot = tree.construct(preOrder, sizeof(preOrder)/sizeof(int), inOrder, sizeof(inOrder)/sizeof(int));
        assertTrue(newRoot != nullptr);
        preorder(newRoot); std::cout << std::endl;
        inorder(newRoot); std::cout << std::endl;
        postorder(newRoot); std::cout << std::endl;
        freePostorder(newRoot);
    }

}
